Random numbers have applications in numerous areas including game playing, statistical sampling, evaluating integral equations, particle transport calculations, and computations in statistical physics, just to name a few. As a result, random number generators (“RNGs”) figure prominently in methods and systems that use random numbers. For example, RNGs are key components of secure systems and are used extensively to generate keys for cryptography. An ideal RNG generates numbers which cannot be predicted in advance and cannot be reliably reproduced. In other words, RNGs ideally generate a sequence of unbiased random numbers. However, many commonly used RNGs either generate sequences of seemingly random numbers or may be susceptible to generating biased sequences of numbers.
RNGs have been implemented in software to generate sequences of seemingly random numbers using formulas and/or numerical methods. Software-based RNGs are referred to as “pseudorandom number generators,” because the formulas allow for prediction and reproduction of a sequence of pseudorandom numbers, provided the same initial parameters are used. A recursive Lehmer pseudorandom number generator (“LPNG”) is an example of a commonly used pseudorandom number generator given by:xn+1=Axn+C(mod M)where
xn is the nth number of a sequence of random numbers; and
A, C, and M are parameters that can be adjusted to ensure that a sequence of numbers generated by the LPNG appears random.
Typically, M is assigned the word size of a computer employed to compute a sequence of pseudorandom numbers, and x0, the seed, is assigned a prime number. For example, assigning A, C, and M the values 21, 1, and 32 (5 bits), respectively, and assigning x0 the prime number 13, the LPNG generates a sequence of pseudorandom integers 13, 18, 27, 24, 25, 14, 7, etc. Alternative approaches may seed a pseudorandom number generator with the time produced by a computer-system clock each time the pseudorandom number generator is initiated. However, even using the time provided by a system clock is not infallible because one can determine the time when the pseudorandom number generator was initiated.
Hardware-based RNGs have also been developed to generate sequences of random numbers from chaotic fluctuations observed in thermal noise generated by atomic, molecular, and electrical systems. For example, thermal noise is generated by an electric current flowing through an electrical conductor, which can be used as a source of a sequence of random numbers by measuring voltage equilibrium fluctuations. The thermal noise occurs whether or not there is an applied voltage because of random motion of electrons in the conductor. However, hardware-based RNGs are not always reliable sources of sequences of random numbers because the systems employed by the hardware-based RNGs are susceptible to environmental changes. For example, an electric noise-based RNG used to generate a sequence of random numbers can be biased by changing the temperature of the system. In addition, the methods typically employed to authenticate the randomness of the sequence generated by a hardware-based RNG are deterministic software based methods that can be used to determine whether the sequences are statistically well-behaved but cannot evaluate the randomness of the sequence.
Another type of RNG, called a “quantum random number generator” (“QRNG”), is based on quantum-mechanical properties of quantum systems. QRNGs are typically employed to generate random numbers by performing measurements on identical quantum systems. Each measurement projects the state of each quantum system onto one of many possible states at the time a measurement is performed. The state determined by the measurement is associated with a number. A number generated in this manner is truly random, because, according to the standard interpretation of quantum mechanics, no amount of refinement of the measurement methods and systems can overcome this uncertainty. As a result, QRNGs are highly desirable systems for generating sequences of random numbers.
Quantum systems comprising just two discrete states, represented by “|0” and “|1,” can be used to implement QRNGs. Examples of two-state quantum systems include any two photon, or energy, states of an electromagnetic field, vertical and horizontal polarization states of an electromagnetic field, and the two spin states of an electron or some atomic nuclei. A quantum system with two discrete states is called a “qubit system,” and the states |0 and |1, called “qubit basis states,” can also be represented in set notation as {|0,|1}. A qubit system can exist in the state |0, the state |1, or in any of an infinite number of states that simultaneously comprise both |0 and |1. Any of the states that include both |0 and/or |1 can be represented mathematically as a linear superposition of states:|ψ=α|0+β|1The state |ψ is called a “qubit,” and the parameters α and β are complex-valued coefficients satisfying the condition:|α|2+|β|2=1When |0 and |1 are the two possible states determined by a measurement performed on the qubit system in the state |ψ, one has a probability |α|2 of finding the qubit system in the state |0 and a probability |β|2 of finding the qubit system in the state |1. One is said to be performing a measurement on the qubit system in the basis {|0,|1}.
The infinite number of states associated with a qubit system can be geometrically represented by a unit-radius, three-dimensional sphere called a “Bloch sphere”:
                  ψ      〉        =                            cos          ⁡                      (                          θ              2                        )                          ⁢                            0          〉                    +                        ⅇ                      ⅈ            ⁢                                                  ⁢            ϕ                          ⁢                  sin          ⁡                      (                          θ              2                        )                          ⁢                            1          〉                      where            0      ≤      θ      <      π        ,    and        0    ≤    ϕ    <          2      ⁢                          ⁢              π        .            FIG. 1 illustrates a Bloch sphere representation of a qubit system. As shown in FIG. 1, lines 101-103 are orthogonal x, y, and z Cartesian coordinate axes, respectively, and a Bloch sphere 106 is centered at the origin. There are an infinite number of points on the Bloch sphere 106, each point representing a unique state of a qubit system. For example, a point 108 on the Bloch sphere 106 represents a unique state of a qubit system that simultaneously comprises, in part, the state |0 and, in part, the state |1. However, once the state of the qubit system is measured in the basis {|0,|1}, the state of the qubit system is projected onto the state |0 110 or onto the state |1 112.
FIG. 2 illustrates a hypothetical single polarizing beamsplitter-based QRNG 200. The QRNG 200 comprises a polarizing beamsplitter 202, two photon detectors 204 and 206, and a photon source 208. The beamsplitter 202 comprises a multilayer dielectric thin film 210 sandwiched between two prisms 212 and 214. The beamsplitter 202 has an input channel 216 and two output channels 218 and 220. The channels 216, 218, and 220 represent either optical fibers or free space. The beamsplitter 202 reflects vertically polarized electromagnetic radiation and transmits horizontally polarized electromagnetic radiation. The photon source 208 outputs a single photon of electromagnetic radiation in an unbiased, coherent linear superposition of states:
          χ    〉    =                    1                  2                    ⁢                      V        〉              +                  1                  2                    ⁢                      H        〉            where
|V represents a vertical polarization state of the photon; and
|H represents a horizontal polarization state of the photon.
The vertical and horizontal polarization states, |V and |H, are orthogonal basis states of the single photon quantum system. The photon remains in the state |χ until the photon is detected at either the photon detector D1 204 or the photon detector D2 206. The square of the coefficients of the state |χ indicates that there is a ½ probability of detecting the photon at the detector D1 204 and a ½ probability of detecting the photon at the detector D2 206. As a result, detection of the photon at either photon detector is a random event.
The QRNG 200 can be used to generate a sequence of random binary numbers which can be partitioned into a sequence of random n-bit words. The sequence of random n-bit words can be used in a variety of random-number applications. For example, the QRNG 200 can be used to generate a sequence of random integers between 0 and 31 as follows. When a photon is detected by the detector D2 206, the binary number “1” is added to a sequence of binary numbers, and when a photon is detected by the detector D1 204, the binary number “0” is added to the same sequence of binary numbers. Suppose that generating the state |χ 30 times generates the following sequence of random binary numbers:                000110101011100101010111100100The sequence of random binary numbers can be partitioned into 5-bit words to give a random sequence of base 2 numbers 00011, 01010, 11100, 10101, 01111, and 00100, which can then be translated into a corresponding sequence of random base 10 integers 3, 10, 28, 21, 15, and 4, respectively.        
Although the QRNG 200 appears to offer a convenient method and system for generating a sequence of random numbers, the QRNG 200 may be susceptible to generating sequences of pseudorandom numbers by tampering with the photon source 208. For example, an adversary with control of the photon source 208 can bias the photon source 208 to output photons represented by the state:
          χ    〉    =                    1                  3                    ⁢                      V        〉              +                            2          3                    ⁢                      H        〉            As a result, the QRNG 200 generates biased sequences of binary numbers with approximately ⅔ of the binary numbers equal to “1” and approximately ⅓ of the binary numbers equal to “0.” Moreover, the methods typically employed to authenticate the randomness of a sequence generated by a device, such as the QRNG 200, are often deterministic software based methods, which as described above are not true RNGs and, therefore, are reliable for authenticating the randomness of a sequence. Physicists, cryptographers, computer scientists, and quantum-information users have recognized a need for QRNGs that can reliably generate sequences of random numbers, and can also detect, authenticate, and correct biases in the sequences of random numbers using methods that rely on the non-deterministic properties of quantum systems.